package org.aplombh.java.leetcode.all;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

public class _30串联所有单词的子串 {
}

class Solution30_1 {
    public List<Integer> findSubstring(String s, String[] words) {

        List<Integer> ans = new ArrayList<>();

        int n = words.length;
        int m = words[0].length();

        int len = n * m;

        for (int left = 0; left + len <= s.length(); left ++) {

            int right = left + len;

            TreeMap<String, Integer> map = new TreeMap<>();

            for (String word : words) {
                if (map.containsKey(word)) map.put(word, map.get(word) + 1);
                else map.put(word, 1);
            }

            for (int j = left; j+m <= right; j += m) {
                String word = s.substring(j, j + m);
                if (map.containsKey(word)) map.put(word, map.get(word) - 1);
                else break;
                if (map.get(word) == 0)
                    map.remove(word);
            }

            if (map.isEmpty())
                ans.add(left);
        }

        return ans;

    }
}